package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:53 2020/8/19
 * @Description 路径总和 II
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    说明: 叶子节点是指没有子节点的节点。
    示例:
    给定如下二叉树，以及目标和 sum = 22，

                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    返回:
    [
       [5,4,11,2],
       [5,8,4,5]
    ]

 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class PathSum {

    List<List<Integer>> ans = new ArrayList<>();

    /**
     * 使用递归，和判断路径和相似
     * @param root
     * @param sum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return Collections.emptyList();
        LinkedList<Integer> list = new LinkedList<>();
        helper(root, sum, list);
        return ans;
    }


    private void helper(TreeNode root, int sum, LinkedList<Integer> list) {
        if (root == null) return;
        //剪枝
        if (root.val > sum && root.left == root.right) {
            return;
        }
        list.addLast(root.val);
        if (sum == root.val && root.left == root.right) {
            ans.add(new ArrayList<>(list)); //此处一定要new一个新的数组，不然数组会共享值
        }
        helper(root.left, sum - root.val, list);
        helper(root.right, sum - root.val, list);
        list.removeLast();
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
